package com.ztom.dp;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 环形子数组的最大和
 * <p>
 * https://leetcode-cn.com/problems/maximum-sum-circular-subarray/
 *
 * @author ZhangTao
 */
public class Code11MaxSubarraySumCircular {

    public static void main(String[] args) {
        int[] nums = {3,1,3,2,6};
        new Code11MaxSubarraySumCircular().maxSubarraySumCircular(nums);
    }
    /**
     * 环形数组转化
     * [1,2,3] ==> [1,2,3,1,2,3]
     * 然后转前缀和数组
     * 使用窗口内最小值的更新结构
     * 找到窗口内最小值, 右侧大值 - 小值 = 最大值
     *
     * @param nums
     * @return
     */
    public int maxSubarraySumCircular(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int n = nums.length;
        if (n == 1) {
            return nums[0];
        }
        // 转化并求得前缀和数据
        int[] help = new int[2 * n];
        help[0] = nums[0];
        for (int i = 1; i < help.length; i++) {
            help[i] = help[i - 1] + nums[i % n];
        }

        int max = help[0];
        // 存的是下标, 由于限定是 nums 的子数组, 所以可以看做窗口最大值为 n
        Deque<Integer> qmin = new LinkedList<>();
        for (int i = 0; i < help.length; i++) {
            // 先检查过期
            if (!qmin.isEmpty() && qmin.peekFirst() < i - n) {
                qmin.pollFirst();
            }
            max = qmin.isEmpty() ? help[i] : Math.max(max, help[i] - help[qmin.peekFirst()]);

            while (!qmin.isEmpty() && help[qmin.peekLast()] >= help[i]) {
                qmin.pollLast();
            }
            qmin.offerLast(i);
        }
        return max;
    }
}
